#include <bits/stdc++.h>

using namespace std;

// KMP算法模版
// 测试链接 : https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

class Solution 
{
public:
    int strStr(string s1, string s2) 
    {
        // return s1.find(s2);
        return kmp(s1, s2);
    }

    // KMP算法
    int kmp(string& s1, string& s2)
    {
		// s1中当前比对的位置是x
		// s2中当前比对的位置是y
        int n = s1.size(), m = s2.size(), x = 0, y = 0;
        // O(m)
        vector<int> next = nextArray(s2, m);
        while(x < n && y < m)
        {
            if(s1[x] == s2[y])
            {
                ++x;
                ++y;
            }
            else if(y == 0)
            {
                ++x;
            }
            else
            {
                y = next[y];
            }
        }
        return y == m ? x - y : -1;
    }

    // 得到next数组
    vector<int> nextArray(string& s, int m)
    {
        if(m == 1) return {-1};
        vector<int> next(m);
        next[0] = -1, next[1] = 0;
		// i表示当前要求next值的位置
		// cn表示当前要和前一个字符比对的下标
		int i = 2, cn = 0;
        while(i < m)
        {
            if(s[i - 1] == s[cn])
                next[i++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[i++] = 0;
        }
        return next;
    }
};


class Solution 
{
public:
    int strStr(string s, string p) 
    {
        int m = s.size(), n = p.size();
        s = ' ' + s;
        p = ' ' + p;
        // 计算 next
        int next[n + 1];
        next[1] = 0;
        for(int i = 2, j = 0; i <= n; ++i)
        {
            while(j && p[i] != p[j + 1]) j = next[j];
            if(p[i] == p[j + 1]) ++j;
            next[i] = j;
        }
        // KMP 匹配
        for(int i = 1, j = 0; i <= m; ++i)
        {
            while(j && s[i] != p[j + 1]) j = next[j];
            if(s[i] == p[j + 1]) ++j;
            if(j == n) return i - n;
        }
        return -1;
    }
};